package leetcode.year2021.month10;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 98. 验证二叉搜索树
 */
public class _24_01IsValidBST98 {
  /**
   * 思路： 还是使用递归， 左边的值小于父节点小于右边的值，然后再判断左边、右边是不是二叉搜索树(思路错误，只校验了左子树小于根节点小于右子树)
   * <p>
   * // 思路2： 中序遍历该树，结果一定是排序的(还是使用递归)
   *
   * @param root
   * @return
   */
  public boolean isValidBST(TreeNode root) {
    return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
  }

  private boolean dfs(TreeNode root, long minValue, long maxValue) {
    if (root == null) {
      return true;
    }
    if (!dfs(root.left, minValue, root.val)) {
      return false;
    }
    if (root.val >= maxValue || root.val <= minValue){
      return false;
    }
    if (!dfs(root.right,root.val,maxValue)){
      return false;
    }
    return true;
  }


// 使用了栈，解题效率不高
//  public boolean isValidBST(TreeNode root) {
//    Deque<Integer> treeVal = new LinkedList<>();
//    return dfs(root,treeVal);
//  }
//
//  private Boolean dfs(TreeNode root, Deque<Integer> treeVal) {
//    if (root == null){
//      return true;
//    }
//    if (root.left != null) {
//      if (!dfs(root.left,treeVal)) {
//        return false;
//      }
//    }
//    if (!treeVal.isEmpty() && treeVal.getLast() >= root.val){
//      return false;
//    } else {
//      treeVal.add(root.val);
//    }
//    if (root.right != null) {
//      if (!dfs(root.right,treeVal)) {
//        return false;
//      }
//    }
//    return true;
//  }

  // 错误解答
//    if (root == null){
//      return true;
//    }
//    if (root.left != null){
//      if (root.left.val >= root.val) {
//        return false;
//      }
//      if (!isValidBST(root.left)) {
//        return false;
//      }
//    }
//    if (root.right != null){
//      if (root.right.val <= root.val){
//        return false;
//      }
//      if (!isValidBST(root.right)) {
//        return false;
//      }
//    }
//    return true;

  /**
   * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
   * <p>
   * 有效 二叉搜索树定义如下：
   * <p>
   * 节点的左子树只包含 小于 当前节点的数。
   * 节点的右子树只包含 大于 当前节点的数。
   * 所有左子树和右子树自身必须也是二叉搜索树。
   */
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
      this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }
}
